# 循环链表节点
class CircularListNode:
    def __init__(self, x):
        self.val = x  # 链表节点的数据域
        self.next = None  # 链表节点的指针域


# 添加操作：给循环链表追加节点
def append_node(head, val):
    if head is None:
        return
    cur = head
    # 1. 移动指针变量到末尾节点
    while cur.next is not head:
        cur = cur.next
    # 2. 新节点追加到末尾节点
    new_node = CircularListNode(val)
    cur.next = new_node
    new_node.next = head  # 更改末尾节点的指向


# 打印循环链表
def print_node(head):
    if head is None:
        return
    cur = head.next
    if head is cur:  # 只有一个节点
        print(cur.val)
        return

    # 1. 打印头节点
    print(head.val, end="\t")
    # 2. 遍历打印下一个节点
    while cur is not head:
        print(cur.val, end="\t")
        cur = cur.next
    print()


# 删除操作，删除第k个节点（返回删除的节点）
def remove_node(head, k):
    if head is None or head is head.next:
        return head
    # 情况1：删除的节点为头节点
    if k == 0:
        cur = head
        # 找到末尾节点
        while cur.next is not head:
            cur = cur.next
        # 更改末尾节点的指针域
        cur.next = head.next
        return head
    # 情况2：删除的节点为 非头节点
    cur = head
    for i in range(k - 1):
        cur = cur.next
    tmp = cur.next  # 删除的节点
    cur.next = cur.next.next  # 删除节点操作
    return tmp  # 返回删除的节点


def josephus(n, m):
    # 1. 创建一个循环链表
    head = CircularListNode(1)
    head.next = head  # 构成环链表
    # 2.  添加节点
    for i in range(1, n):
        append_node(head, i + 1)
    print_node(head)

    # 3. 依次删除链表节点
    for j in range(n):
        node = remove_node(head, m - 1)
        print(node.val, end="\t")
        head = node.next  # 下次开始时，开始节点为删除节点的下一个节点
    print()


if __name__ == '__main__':
    # josephus(6, 5)
    # josephus(6, 1)
    josephus(41, 3)
